/*
  ! 前途似海，来日方长。
  ! Created: 2024/12/04 11:07:38
*/
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
// #define int long long
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for (int i = (x); i <= (y); i++)
#define pre(i, x, y) for (int i = (x); i >= (y); i--)
inline void JYFILE19();

using i64 = long long;
using pii = pair<int, int>;

bool ST;
const int N = 1e6 + 10;
const int mod = 998244353;

int c, t;

namespace Math {
int Fc[1000010], Iv[1000010];
template<typename T> inline void add(T&x, int y) { if ((x += y) >= mod) x -= mod; }
template<typename T> inline void del(T&x, int y) { if ((x -= y) < 0) x += mod; }
template<typename T> inline void add(T&x, int y, int z) { x = (x + (long long) y * z) % mod; }
template<typename T> inline void mo(T&x) { x = (x % mod + mod) % mod; }
inline long long power(long long x, long long y) {
  long long res = 1;
  while (y) { if (y & 1) res = res * x % mod; x = x * x % mod, y /= 2; }
  return res;
}
inline void init(int n) {
  Fc[0] = 1;
  for (int i = 1; i <= n; i++) Fc[i] = (long long) Fc[i - 1] * i % mod; Iv[n] = power(Fc[n], mod - 2);
  for (int i = n; i >= 1; i--) Iv[i - 1] = (long long) Iv[i] * i % mod;
}
inline long long C(int x, int y) { return (x < 0 || y < 0 || x < y ? 0 : (long long) Fc[x] * Iv[y] % mod * Iv[x - y] % mod); }
}
namespace subtask0 {
  int n, m, ct;
  int u[N], v[N], hd[N], dp[N];
  struct edge { int to, nxt; } e[N << 1];
  inline void solve() {
    cin >> n >> m;
    fro(i, 1, m) cin >> u[i] >> v[i];
    int ns = -1e9;
    fro(i, 1, m) {
      fro(j, 1, m) {
        if (i == j) continue;
        e[++ct] = {u[j], hd[v[j]]}, hd[v[j]] = ct;
        e[++ct] = {v[j], hd[u[j]]}, hd[u[j]] = ct;
      }
      queue<int> q;
      q.push(u[i]);
      dp[u[i]] = 1;
      while (q.empty() == 0) {
        int x = q.front(); q.pop();
        if (x == v[i]) { ns = max(ns, 2 - m - dp[x]); break; }
        for (int j = hd[x]; j; j = e[j].nxt)
          if (!dp[e[j].to]) dp[e[j].to] = dp[x] + 1, q.push(e[j].to);
      }
      fill(dp + 1, dp + n + 1, 0);
      fill(hd + 1, hd + n + 1, ct = 0);
    }
    cout << ns << " " << 0 << "\n";
  }
}
namespace subtask1 {
  int n, m, k, ct;
  int u[88], v[88];
  int a[88], b[88], f[88][88];
  inline void solve() {
    cin >> n >> m, k = 0;
    fro(i, 1, m) cin >> u[i] >> v[i];
    fro(i, 1, n) fro(j, i + 1, n) ++k, a[k] = i, b[k] = j;
    i64 ns1 = -1e18, ns2 = 0;
    fro(i, 1, (1 << k) - 1) {
      if (__builtin_popcount(i) == m - 1) {
        fro(j, 1, n) fro(k, 1 ,n) f[j][k] = 1e9;
        fro(j, 1, n) f[j][j] = 0;
        fro(j, 1, k)
          if ((i >> j - 1) & 1) {
            f[a[j]][b[j]] = 1;
            f[b[j]][a[j]] = 1;
          }
        fro(j, 1, n) fro(l, 1, n) fro(r, 1, n) f[l][r] = min(f[l][r], f[l][j] + f[j][r]);
        i64 sm = 0;
        fro(j, 1, m) sm -= f[u[j]][v[j]];
        if (ns1 < sm) {
          ns1 = sm;
          ns2 = 1;
        } else if (ns1 == sm) {
          ns2++;
        }
      }
    }
    cout << ns1 << " " << ns2 << "\n";
  }
}
namespace subtask2 {
  int n, m;
  inline void solve() {
    cin >> n >> m, n--;
    fro(i, 1, m) { int x, y; cin >> x >> y; }
    cout << -2 * n << " " << Math::C(3 * n, n) * Math::power(2 * n + 1, mod - 2) % mod << "\n";
  }
}
namespace subtask3 {
  int n, m, ct;
  int u[N], v[N], hd[N], dp[N];
  struct edge { int to, nxt; } e[N << 1];
  inline void solve() {
    cin >> n >> m;
    fro(i, 1, m) cin >> u[i] >> v[i];
    int ns = -1e9;
    int sz = 0;
    fro(i, 1, m) {
      fro(j, 1, m) {
        if (i == j) continue;
        e[++ct] = {u[j], hd[v[j]]}, hd[v[j]] = ct;
        e[++ct] = {v[j], hd[u[j]]}, hd[u[j]] = ct;
      }
      queue<int> q;
      q.push(u[i]);
      dp[u[i]] = 1;
      while (q.empty() == 0) {
        int x = q.front(); q.pop();
        if (x == v[i]) {
          if (ns == 2 - m - dp[x]) sz++;
          if (ns < 2 - m - dp[x]) ns = 2 - m - dp[x], sz = 1;
          break;
        }
        for (int j = hd[x]; j; j = e[j].nxt)
          if (!dp[e[j].to]) dp[e[j].to] = dp[x] + 1, q.push(e[j].to);
      }
      fill(dp + 1, dp + n + 1, 0);
      fill(hd + 1, hd + n + 1, ct = 0);
    }
    n = 1 - m - ns;
    cout << ns << " " << sz * Math::C(3 * n, n) % mod * Math::power(2 * n + 1, mod - 2) % mod * Math::power(n + 1, mod - 2) % mod << "\n";
  }
}

signed main() {
  JYFILE19();
  cin >> c >> t;
  Math::init(10000);
  while (t--) {
    if (1 <= c && c <= 2) subtask1::solve();
    if (3 <= c && c <= 4) subtask2::solve();
    if (5 <= c && c <= 6) subtask3::solve();
    if (7 <= c) subtask0::solve();
  }
  return 0;
}

bool ED;
inline void JYFILE19() {
  freopen("oi.in", "r", stdin);
  freopen("oi.out", "w", stdout);
  srand(random_device{}());
  ios::sync_with_stdio(0), cin.tie(0);
  double MIB = fabs((&ED - &ST) / 1048576.), LIM = 512;
  cerr << "MEMORY: " << MIB << endl, assert(MIB <= LIM);
}